package problem310;

//310.最小高度树
//https://leetcode.cn/problems/minimum-height-trees/description/?envType=problem-list-v2&envId=depth-first-search

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if(n == 1) {
            res.add(0);
            return res;
        }
        int[] degree = new int[n];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int[] e : edges) {
            degree[e[0]]++;
            degree[e[1]]++;
            if(!map.containsKey(e[0])) {
                map.put(e[0], new HashSet<>());
            }
            if(!map.containsKey(e[1])) {
                map.put(e[1], new HashSet<>());
            }
            map.get(e[0]).add(e[1]);
            map.get(e[1]).add(e[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            if(degree[i] == 1) {
                queue.add(i);
            }
        }

        while(!queue.isEmpty()) {
            res = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i<size; i++) {
                int t = queue.poll();
                res.add(t);
                Set<Integer> set = map.get(t);
                for(int x : set) {
                    map.get(x).remove(t);
                    degree[x]--;
                    if(degree[x] == 1) {
                        queue.add(x);
                    }
                }
            }
        }

        return res;
    }
}